/*================================================================
*   Copyright (C) 2024 baichao All rights reserved.
*
*   文件名称：main.c
*   创 建 者：baichao
*   创建日期：2024年01月09日
*   描    述：
*
================================================================*/

/*
 * 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target
 * 。该矩阵具有以下特性： 每行的元素从左到右升序排列。
 * 每列的元素从上到下升序排列。
 *
 * 示例 1：
 *   输入：matrix =
 * [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]],
 * target = 5 输出：true
 *
 * 示例 2：
 *   输入：matrix =
 * [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]],
 * target = 20 输出：false
 *
 *
 * 提示：
 *   m == matrix.length
 *   n == matrix[i].length
 *   1 <= n, m <= 300
 *   -109 <= matrix[i][j] <= 109
 *   每行的所有元素从左到右升序排列
 *   每列的所有元素从上到下升序排列
 *   -109 <= target <= 109
 */

#include <stdbool.h>
#include <stdio.h>

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize,
                  int target) {
  int m = matrixSize - 1, n = (*matrixColSize - 1);
  int row = 0, col = n;

  while (1) {
    if (target == matrix[row][col]) {
      return true;
    } else if (target < matrix[row][col]) {
      col--;
    } else {
      row++;
    }

    if (row > m || col < 0) {
      break;
    }
  }

  return false;
}

int main() {
  // int matrixData[][5] = {{1, 4, 7, 11, 15},
  //                        {2, 5, 8, 12, 19},
  //                        {3, 6, 9, 16, 22},
  //                        {10, 13, 14, 17, 24},
  //                        {18, 21, 23, 26, 30}};
  int matrixData[][1] = {{-5}};
  int matrixSize = sizeof(matrixData) / sizeof(matrixData[0]);
  int matrixColSize = 1;

  int* matrix[matrixSize];
  for (int i = 0; i < matrixSize; i++) {
    matrix[i] = matrixData[i];
  }

  int target = -10;

  bool result = searchMatrix(matrix, matrixSize, &matrixColSize, target);

  printf("Target %d %s found in the matrix.\n", target,
         result ? "is" : "is not");

  return 0;
}